\chapter{Вопрос № 27}

Композиция опф как бинарная операция на множестве таких функций. Сведение задачи о перечислении корневых деревьев к задача поиска обратного элемента по отношению к операции композиции опф. Алгоритм поиска количества корневых помеченных деревьев.

\section{Множество опф и операция композиции}

На множестве опф задана операция композиции опф. Эта операция является ассоциативной, а само множество является полугоруппой. Нейтральным элементом на множестве опф относительно композиции очевидно является опф $e\left(x\right) = x$. Полугруппа с нейтральным элементом - моноид.

Наконец, если для каждого элемента $f$ множества существует элемент $g$ из этого множества, такой что $fg = e$, то моноид называется группой, а элементы $f$ и $g$ взаимообратными элементами, а само множество называется группой, в нашем случае обратимы относительно операции композиции только опф вида:
\[
	f\left(x\right) = a_1 x + a_2 x^2 + a_3 x^3 + ...
\]
где $a_1 \not= 0$.

\section{Поиск обратного элемента}

Допустим $g\left(f\left(x\right)\right) = x$, тогда если через $a_i$ обозначить коэффициенты $f\left(x\right)$, а через $b_i$ коэффициенты $g\left(x\right)$, тогда:
\[
	b_1\left(a_1x + a_2x^2 + ...\right) + b_2\left(a_1x + a_2x^2 + ... \right)^2 + b_3\left(a_1x+a_2x^2+ ...\right)^3 + ... = x
\]
далее приравнивая коэффициенты при степенях $x$ слева и справа получаем бесконечную систему уравнений, начинающуюся следующим образом:
\[
	\begin{split}
		& b_1a_1 = 1 \Leftrightarrow b_1 = \frac{1}{a_1} \\
		& b_1a_2 + b_2a_1^2 = 0 \Leftrightarrow b_2 = -\frac{b_1a_2}{a_1^2} = -\frac{a_2}{a_1^3} \\
		& b_1a_3 + 2b_2a_1a_2 + b_3a_1^3 = 0 \Leftrightarrow b_3 = -\frac{b_1a_3 + 2b_2a_1a_2}{a_1^3} = ...
	\end{split}
\]

\section{Перечисление корневых деревьев}

Имеется функциональное уравнение:
\begin{equation}
	T\left(x\right) = xe^{T\left(x\right)}
\end{equation}
в котором $T\left(x\right)$ - эпф, перечисляющая корневые помеченные деревья. Введем обозначение $\hat t_n = \frac{t_n}{n!}$, таким образом перейдем от эпф к опф:
\[
	\hat T\left(x\right) = \hat t_1 x + \hat t_2 x^2 + \hat t_3 x^3 + ...
\]
кроме того:
\[
	\phi\left(x\right) = e^x = 1+x+\frac{x^2}{2!} + \frac{x^3}{3!} + ...
\]
и будем считать ее опф (перечисляет числа $\frac{1}{n!}$), тогда:
\[
	\hat T\left(x\right) = x \phi\left(\hat T\left(x\right)\right) \Leftrightarrow \frac{\hat T\left(x\right)}{\phi\left(\hat T\left(x\right)\right)} = x
\]
теперь введем опф:
\[
	f\left(x\right) = xe^{-x}
\]
то получим, что композиция опф:
\[
	f\left(\hat T\left(x\right)\right) = x
\]
теперь пользуясь предыдущими результатами об обращении получаем, что:
\[
	\begin{split}
		& \hat T\left(x\right) = \hat t_1 x + \hat t_2 x^2 + \hat t_3 x^3 + ... \\
		& f\left(x\right) = xe^{-x} = x - x^2 + \frac{1}{2!}x^3 - \frac{1}{3!}x^4 + ... \\
		& \hat t_1 \left(x-x^2+\frac{1}{2!}x^3 - \frac{1}{3!}x^4 + ...\right) + t_2\left(x-x^2 + \frac{1}{2!}x^3-\frac{1}{3!}x^4+...\right)^2 + \\
		& + \hat t_3\left(x-x^2+\frac{1}{2!}x^3-\frac{1}{3!}x^4+...\right)^3 + ... = x
	\end{split}
\]
далее выписываем систему уравнений:
\[
	\begin{split}
		& \hat t_1 = 1 \Rightarrow t_1 = 1\\
		& -\hat t_1 + \hat t_2 = 0 \Rightarrow \hat t_2 = 1 \rightarrow t_2 = 2!\hat t_2 = 2 \\
		& \hat t_1 \frac{1}{2!} - 2 \hat t_2 + \hat t_3 = 0 \Rightarrow \hat t_3 = 2 - \frac{1}{2} = 3/2 \Rightarrow t_3 = 3! \frac{3}{2} = 9
	\end{split}
\]
таким образом получили алгоритм для поиска количества корневых помеченных деревьев, а вместе с ними и просто помеченных деревьев.
